package com.darrenchan.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-02 00:27
 */
public class Q257 {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        List<String> subsets = new ArrayList<>();
        subsets.add(root.val + "");
        dfs(root, subsets, res);
        return res;
    }

    private void dfs(TreeNode root, List<String> subsets, List<String> res) {
        if (root != null && root.left == null && root.right == null) {
            String path = String.join("->", subsets);
            res.add(path);
        }

        if (root.left != null) {
            subsets.add(root.left.val + "");
            dfs(root.left, subsets, res);
            subsets.remove(subsets.size() - 1);
        }

        if (root.right != null) {
            subsets.add(root.right.val + "");
            dfs(root.right, subsets, res);
            subsets.remove(subsets.size() - 1);
        }
    }
}
